package lib.tree;

import java.util.ArrayList;
import java.util.List;

import lib.util.Mutable;

/**
 * Tree utility
 * 
 * @author <a href="http://www.sureinterview.com">sureinterview</a>
 * 
 */
public class TreeUtil {
	private Integer curVal;
	private int pos;
	private char[] treeStr;

	/**
	 * Recursive inorder binary tree traversal
	 * 
	 * @param tree
	 *            a binary tree
	 * @return the inorder node list
	 */
	public List<Integer> inorder(BNode tree) {
		List<Integer> lst = new ArrayList<Integer>();
		inorderRec(tree, lst);
		return lst;
	}

	void inorderRec(BNode tree, List<Integer> lst) {
		// 1. precondition. or setup some condition.
		if (tree == null)
			return;

		// 2. inorder traversal
		// - 2.1 left
		inorderRec(tree.left, lst);
		// - 2.2 root
		lst.add(tree.value);
		// - 2.3 right
		inorderRec(tree.right, lst);

		// 3. clean up
	}

	/**
	 * check if a tree is BST (binary search tree) by definition (left < root <=
	 * right)
	 * 
	 * @param tree
	 *            binary tree
	 * @return true if the tree is BST. otherwise, false.
	 */
	public boolean isBST(BNode tree) {
		return isBSTrec(tree, new Mutable<Integer>(), new Mutable<Integer>());
	}

	/**
	 * check if a tree is BST (binary search tree) by a normal inorder traversal
	 * (left < root <= right)
	 * 
	 * @param tree
	 *            binary tree
	 * @return true if the tree is BST. otherwise, false.
	 */
	public boolean isBST2(BNode tree) {
		curVal = Integer.MIN_VALUE;
		return isBST2rec(tree);
	}

	private boolean isBST2rec(BNode root) {
		// 1 setup, precondition
		if (root == null)
			return false;

		// 2 traversal
		// - 2.1 left
		if (root.left != null && !isBST2rec(root.left))
			return false;

		// - 2.2 root
		// check the root against previous value. According to definition, it is
		// not possible that the maximum (the last number) is great or equal to
		// the root
		if (root.value < curVal)
			return false;

		// if the last value comes from left child, also check ==.
		if (root.left != null && root.equals(curVal))
			return false;

		curVal = root.value;

		// - 2.3 right
		if (root.right != null && !isBST2rec(root.right))
			return false;

		// 3 clean up
		return true;
	}

	/**
	 * check BST by definition
	 * 
	 * @param root
	 *            the tree to check against
	 * @param min
	 *            the minimum number in the tree (the left most node)
	 * @param max
	 *            the maximum number in the tree (the right most node)
	 * @return if the tree is BST
	 */
	private boolean isBSTrec(BNode root, Mutable<Integer> min,
			Mutable<Integer> max) {

		// 1. setup, or precondition check
		if (root == null)
			return false;

		Mutable<Integer> tMin = new Mutable<Integer>();
		Mutable<Integer> tMax = new Mutable<Integer>();

		// 2. traversal structure
		// - 2.1 left
		if (root.left != null) {
			if (!isBSTrec(root.left, tMin, tMax))
				return false;
			if (tMax.getValue() >= root.value)
				return false;
			min.setValue(tMin.getValue());
		} else {
			min.setValue(root.value);
		}

		// - 2.2 root

		// - 2.3 right
		if (root.right != null) {
			if (!isBSTrec(root.right, tMin, tMax))
				return false;
			if (tMin.getValue() < root.value)
				return false;
			max.setValue(tMax.getValue());
		} else {
			max.setValue(root.value);
		}

		// 3 clean up
		return true;
	}

	/**
	 * Make a tree in format like: {value}({left tree},{right tree}).
	 * 
	 * @param tree
	 *            the string
	 * @return the tree
	 */
	public BNode makeTree(String tree) {
		treeStr = tree.toCharArray();
		pos = 0;
		try {
			return makeTreeRec();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return null;
	}

	private BNode makeTreeRec() throws Exception {
		// 1. setup
		BNode root = new BNode();
		char c = treeStr[pos];
		root.value = 0;
		while (c >= '0' && c <= '9') {
			root.value *= 10;
			root.value += c - '0';
			c = treeStr[++pos];
		}

		// 2 left, root, right
		if (c == '(') {
			c = treeStr[++pos];
			if (c != ',') {
				root.left = makeTreeRec();
			}
			if (treeStr[pos] != ',')
				throw new Exception("',' expected at position " + pos);

			c = treeStr[++pos]; // skip ","
			if (c != ')') {
				root.right = makeTreeRec();
			}
			if (treeStr[pos] != ')')
				throw new Exception("')' expected at position " + pos);
			++pos; // --> )
		}

		// 3 clean up
		int size = 1;
		if (root.left != null) {
			root.left.parent = root;
			size += root.left.size;
		}

		if (root.right != null) {
			root.right.parent = root;
			size += root.right.size;
		}

		root.size = size;
		return root;
	}
}
